import java.util.ArrayDeque;
import java.util.Deque;

public class Leetcode2104 {

    public static void main(String[] args) {
        System.out.println(subArrayRanges(new int[]{4, -2, -3, 4, 1}));
    }

    public static long subArrayRanges(int[] nums) {
        long res = 0;

        for (int startIndex = 0; startIndex < nums.length; startIndex++) {
            int min = Integer.MAX_VALUE;
            int max = Integer.MIN_VALUE;
            for (int endIndex = startIndex; endIndex < nums.length; endIndex++) {
                min = Math.min(min, nums[endIndex]);
                max = Math.max(max, nums[endIndex]);
                res += max - min;
            }
        }

        return res;
    }

    class Solution {
        public long subArrayRanges(int[] nums) {
            int n = nums.length;
            int[] minLeft = new int[n];
            int[] minRight = new int[n];
            int[] maxLeft = new int[n];
            int[] maxRight = new int[n];
            Deque<Integer> minStack = new ArrayDeque<>();
            Deque<Integer> maxStack = new ArrayDeque<>();
            for (int i = 0; i < n; i++) {
                while (!minStack.isEmpty() && nums[minStack.peek()] > nums[i]) {
                    minStack.pop();
                }
                minLeft[i] = minStack.isEmpty() ? -1 : minStack.peek();
                minStack.push(i);

                // 如果 nums[maxStack.peek()] == nums[i], 那么根据定义，
                // nums[maxStack.peek()] 逻辑上小于 nums[i]，因为 maxStack.peek() < i
                while (!maxStack.isEmpty() && nums[maxStack.peek()] <= nums[i]) {
                    maxStack.pop();
                }
                maxLeft[i] = maxStack.isEmpty() ? -1 : maxStack.peek();
                maxStack.push(i);
            }
            minStack.clear();
            maxStack.clear();
            for (int i = n - 1; i >= 0; i--) {
                // 如果 nums[minStack.peek()] == nums[i], 那么根据定义，
                // nums[minStack.peek()] 逻辑上大于 nums[i]，因为 minStack.peek() > i
                while (!minStack.isEmpty() && nums[minStack.peek()] >= nums[i]) {
                    minStack.pop();
                }
                minRight[i] = minStack.isEmpty() ? n : minStack.peek();
                minStack.push(i);

                while (!maxStack.isEmpty() && nums[maxStack.peek()] < nums[i]) {
                    maxStack.pop();
                }
                maxRight[i] = maxStack.isEmpty() ? n : maxStack.peek();
                maxStack.push(i);
            }

            long sumMax = 0, sumMin = 0;
            for (int i = 0; i < n; i++) {
                sumMax += (long) (maxRight[i] - i) * (i - maxLeft[i]) * nums[i];
                sumMin += (long) (minRight[i] - i) * (i - minLeft[i]) * nums[i];
            }
            return sumMax - sumMin;
        }
    }

}
